COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00010 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a59.tex[154,phy] \today\hfill}

\parskip 5pt
\line{\bf Finite Fields and Primitive Roots\hfill}

%\smallskip
%\line{\bf Primitive Roots.\hfill}

\medskip

{\rmn
{\narrower\smallskip\noindent
({\bf Paradigm:} prove summation identities by counting a set whole and
partitioned.) 

Example of the paradigm. Count the set of bit strings of length~$N$; there
are $2↑N$ of them. Partition by the number~$i$ of bits after the
first~1: There are~$2↑i$. There is also a string of all zeroes. This gives
$$\sum↓{i=0}↑{N-1}2↑i+1=2↑N\,.$$

\smallskip
Deeper example of the paradigm: Count the number of $(n+1)$-bit strings
in which there are $b+1$ one-bits; the formula is ${n+1\choose b+1}$. Count
those which have the last one-bit in position $i+1$; the formula
is ${i\choose b}$. Summing, $\sum↓{i=0}↑n{i\choose b}={n+1\choose b+1}$.
\smallskip}
}

\proclaim Theorem. $\sum↓{e\mid d}\phi(e)=d$.\par

\noindent
{\bf Proof.} The number of proper fractions $0≤i/d<1$ that have denominator~$d$
is~$d$. After reducing each to lowest terms, all denominators are divisors
of~$d$. For each such 
divisor~$e$, there are all fractions $j/e$ with $0≤j/e<1$ and
$j$~prime to~$e$; there are $\phi(e)$ such~$j$, so another formula for the
number of fractions is $\sum↓{e\mid d}\phi(e)$.
\quad\blackslug

Let $F$ be a finite field with $n$ non-zero elements. The non-zero elements
form a group~$(G,\times)$, so if $a\in G$, $a$~has order~$e$ that divides~$n$;
$a↑e=a↑n=1$. We say $a$ is a primitive $e↑{\rm th}$ root of~1, and an
$n↑{\rm th}$ root of~1.

\proclaim Theorem. In a field there are no more than $e\;e↑{\rm th}$ roots
of any element. {\rm (Proof not given here.)}

If $n=ij$, consider the $n$ ordered pairs $(a,b)$ where
$a\in G$ and $b=a↑i$.
Since $b↑j=a↑{ij}=1$, there are at most $j$~different values of~$b$, and
since $a↑i=b$, there are no more than $i$~values of~$a$ for each~$b$,
for no more than $ij=n$ pairs $(a,b)$ altogether. Since there are
$n$~pairs, there are exactly $j$~values of~$b$, no other $j↑{\rm th}$ roots
of~1, and each $b$ has exactly $i\;i↑{\rm th}$ roots. No other numbers have
$i↑{\rm th}$ roots: if $a↑i=c$, $1=a↑{ij}=c↑j$, and~$c$ is one of
the~$b$'s. 

While every $j↑{\rm th}$ root $b$ of 1 has $i\;i↑{\rm th}$ roots, not all
are primitive $i↑{\rm th}$~roots of~$b$. For example, 1~is a $j↑{\rm th}$~root
of~1, and has roots~1 and~$-1$ of orders~1 and~2, respectively. The
$i↑{\rm th}$ roots of~1 are all the primitive $d↑{\rm th}$ roots of~1, 
where $d\mid i$. Because $i=\sum↓{d\mid i}\phi(d)$, one sees by induction on~$i$
that the number of primitive $i↑{\rm th}$ roots of~1, where $i\mid n$,
is $\phi(i)≠0$; there are primitive $i↑{\rm th}$~roots of~1 for all
$i\mid n$, particularly there are primitive $n↑{\rm th}$~roots of~1, and
$G$ is cyclic. If we pick a random element~$r$ of~$G$, there is
probability $\phi(n)/n$ that it is a primitive root, and if
$n≤3.1666\times 10↑{110}$, this probability is at least 0.1.

The order $p$ of 1 in $(F,+)$ must be a prime because, if $p=kl$, then
$$\underbrace{(1+1+\cdots +1)}↓k\times \underbrace{(1+1+\cdots +1)}↓l=0\,,$$
but fields have no divisors of~0, so $k=p$ or $l=p$. Therefore the
subgroup of $(F,+)$ generated by~1 is the field~$J↓p$. Let $\rho$ be
a {\sl primitive root\/} of~$F$, i.e., a~primitive $n↑{\rm th}$ root of~1 in
$(F',\times)$.

\proclaim Theorem. $|F|$ is a power of $p$.

\noindent{\bf Proof.} $\rho↑n-1=0$, so there is a monic polynomial $x↑n-1$
with coefficients in~$J↓p$ of which $\rho$ is a root. Let $d(x)$ be
such a polynomial of least degree~$e$. Every element of~$F$, being either
zero or a power of~$\rho$, is a polynomial $f(\rho)=f(x)|↓{x=\rho}$.
Express $f(x)\bmod d(x)$ as $f(x)=g(x)d(x)+r(x)$, so
$f(\rho)=r(\rho)$, and $F=\{a↓0+a↓1\rho+a↓2\rho↑2+\cdots +a↓{e-1}\rho↑{e-1}\}$,
all of which are distinct by definition of~$d$, and $|F|=p↑e$.

If $d(x)=g(x)\cdot h(x)$ is reducible in $J↓p[x]$, $0=d(\rho)=g(\rho)\cdot
h(\rho)$, absurd, so $d(x)$ is irreducible. $F$~is isomorphic to the quotient
ring $J↓p[x]/d(x)$ under the correspondence $f(\rho)\leftrightarrow f(x)$.
We conclude:

\proclaim Theorem. Every finite field is a simple extension $J↓p(\rho)$
of some~$J↓p$.\quad\blackslug

The $p-1$ non-zero elements of $J↓p$ all satisfy $x↑{p-1}-1=0$, as do the powers
of $\rho↑{n/(p-1)}$, so

\proclaim Theorem. The powers of $\rho↑{n/(p-1)}$ are the nonzero elements
of~$J↓p$.


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
October 24, 1986.
%revised date;
%subsequently revised.

\bye